package com.practice.niuke.new_direct_basics.class05;

import java.util.LinkedList;
import java.util.Stack;

/**
 * 如何判断一颗二叉树是否是搜索二叉树？
 */
public class Code04_IsBST {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static class ReturnData {
        public boolean isBST;
        public int min;
        public int max;

        public ReturnData(boolean is, int mi, int ma) {
            isBST = is;
            min = mi;
            max = ma;
        }
    }

    public static ReturnData process(Node x) {
        if (x == null) {
            return null;
        }
        ReturnData leftData = process(x.left);
        ReturnData rightData = process(x.right);
        int min = x.value;
        int max = x.value;
        if (leftData != null) {
            min = Math.min(min, leftData.min);
            max = Math.max(max, leftData.max);
        }
        if (rightData != null) {
            min = Math.min(min, rightData.min);
            max = Math.max(max, rightData.max);
        }
//		boolean isBST = true;
//		if(leftData!=null && (!leftData.isBST   ||  leftData.max >= x.value  )) {
//			isBST= false;
//		}
//		if(rightData!=null && ( !rightData.isBST || x.value >= rightData.min   )) {
//			isBST= false;
//		}

        boolean isBST = false;
        if (
                (leftData != null ? (leftData.isBST && leftData.max < x.value) : true)
                        &&
                        (rightData != null ? (rightData.isBST && rightData.min > x.value) : true)
        ) {

            isBST = true;

        }


        return new ReturnData(isBST, min, max);
    }


    public static boolean isF(Node head) {
        if (head == null) {
            return true;
        }
        Info data = f(head);
        return data.nodes == (1 << data.height - 1);
    }

    /**
     * 判断一颗二叉树是否是搜索二叉树时，
     * 递归函数作用于每个节点返回的统一信息：
     *
     * （1）boolean isBST: 整棵子树是否是搜索二叉树
     * （2）int max: 整棵子树的最大值
     * （3）int min: 整棵子树的最小值
     */
    public static class Info1 {
        public boolean isBST;
        public int max;
        public int min;

        public Info1(boolean isBST, int max, int min) {
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        }
    }

    /**
     * 递归函数：以x为头的树，返回Info1（3个信息）
     *
     * @param x 节点
     * @return Info
     */
    public static Info1 process1(Node x) {
        // 基准条件
        if (x == null) {
            return null;
        }

        // x节点的左子树（不包括x节点）返回的三个信息
        Info1 leftData = process1(x.left);
        // x节点的右子树（不包括x节点）返回的三个信息
        Info1 rightData = process1(x.right);

        // 求以x节点为头的子树的最大值和最小值
        int min = x.value;
        int max = x.value;
        if (leftData != null) {
            min = Math.min(min, leftData.min);
            max = Math.max(max, leftData.max);
        }
        if (rightData != null) {
            min = Math.min(min, rightData.min);
            max = Math.max(max, rightData.max);
        }

        // 以x节点为头的子树是否为搜索二叉树
        boolean isBST = false;
        if (
                (leftData != null ? (leftData.isBST && leftData.max < x.value) : true)
                        &&
                        (rightData != null ? (rightData.isBST && rightData.min > x.value) : true)
        ) {
            isBST = true;
        }

        return new Info1(isBST, max, min);
    }

    /**
     * 判断一颗二叉树是否是搜索二叉树
     * (里面调用递归流程)
     *
     * @return boolean
     */
    public static boolean isBSTTest(Node head) {
        Info1 info1 = process1(head);
        return info1.isBST;
    }

    public static class Info {
        public int height;
        public int nodes;

        public Info(int h, int n) {
            height = h;
            nodes = n;
        }

    }

    public static Info f(Node x) {
        if (x == null) {
            return new Info(0, 0);
        }
        Info leftData = f(x.left);
        Info rightData = f(x.right);
        int height = Math.max(leftData.height, rightData.height) + 1;
        int nodes = leftData.nodes + rightData.nodes + 1;
        return new Info(height, nodes);
    }


    public static boolean inOrderUnRecur(Node head) {
        if (head == null) {
            return true;
        }
        int pre = Integer.MIN_VALUE;
        Stack<Node> stack = new Stack<Node>();
        while (!stack.isEmpty() || head != null) {
            if (head != null) {
                stack.push(head);
                head = head.left;
            } else {
                head = stack.pop();
                if (head.value <= pre) {
                    return false;
                }
                pre = head.value;
                head = head.right;
            }
        }
        return true;
    }

    public static boolean isBST(Node head) {
        if (head == null) {
            return true;
        }
        LinkedList<Node> inOrderList = new LinkedList<>();
        process(head, inOrderList);
        int pre = Integer.MIN_VALUE;
        for (Node cur : inOrderList) {
            if (pre >= cur.value) {
                return false;
            }
            pre = cur.value;
        }
        return true;
    }

    public static void process(Node node, LinkedList<Node> inOrderList) {
        if (node == null) {
            return;
        }
        process(node.left, inOrderList);
        inOrderList.add(node);
        process(node.right, inOrderList);
    }

}
